#include <stdio.h>


int findMaxSub(int *arr, int *start, int end)
{
	int i = 0;
	int tmp = arr[end];
	int max = arr[end];
	*start = end;

	for (i = end - 1; i >= 0; i--) {
		tmp += arr[i];

		if (tmp > max) {
			max = tmp;
			*start = i;
		}
	}

	return max;
}

void main()
{
	int arr[] = { 12, 5, -1, 31, -61, 59, 26, -53, 58, 97, -93, -23, 84, -15, 6 };
	int N = 15;

	int OPT[16] = { 0 };
	int start = 0;
	int end = 0;
	int i = 0;
	int tmp = 0;
	int tmpStart = 0;

	OPT[0] = arr[0];
	start = 0;
	end = 0;
	for (i = 1; i < N; i++) {
		OPT[i] = OPT[i - 1];

		if (arr[i] > 0) {
			tmp = findMaxSub(arr, &tmpStart, i);
			if (tmp > OPT[i - 1]) {
				OPT[i] = tmp;
				start = tmpStart;
				end = i;
			}
		}

		printf("OPT[%d]: %d\n", i, OPT[i]);
		
	}

	printf("sum from %d to %d: %d\n", start, end, OPT[N - 1]);

}
